1. Field of the Invention
This invention relates to the field of data addressing, and, in particular, to address generation for error correction in compact disc read-only memory (CD-ROM).
2. Background
Compact disc read-only memory (CD-ROM) is widely used for the storage and disbursement of large amounts of digital information. A single 12 cm CD-ROM disc can store more than 527 megabytes (MB) of data, the equivalent of 200,000 printed pages or more than 375 1.4 MB floppy diskettes. Also, the durable construction of the disc and the nonvolatile nature of the data make CD-ROM ideal for safe data transport.
The CD-ROM disc consists of a clear plastic, called polycarbonate, coated on one surface with a reflective metallic layer and a protective lacquer label. Digital information is stored on the disc in the form of small surface impressions, called "pits," molded into the plastic and the flat gaps between pits, called "lands." The reflective metallic layer is applied over the molded surface of the plastic.
The pits and lands, representing binary data, are laid out in a spiral track roughly 0.6 microns wide at a track density of approximately 16,000 tracks per inch. The spiral track is read outward from the center of the disc with constant linear velocity (CLV). This CLV scheme permits the bit density near the outer edge of the disk to match that near the axis by manipulation of the CD-ROM drive speed. The data is read from the surface of the disc by focusing a laser beam from a laser diode through the clear polycarbonate onto the track. A pit serves to scatter and absorb the laser beam, whereas a land reflects the laser beam into a photodetector. Typically, a CD-ROM drive processes the analog signal from the photodetector to obtain digital data, performs error correction, and provides the digital data to a host computer.
FIG. 1 shows a simplified block diagram of a CD-ROM drive coupled to a host computer. CD-ROM disc 100 rests on a spinning turn table represented by turn table motor 101. The turn table motor receives control signals 113 from turn table motor control block 103 to control the speed and acceleration of the rotating CD-ROM disc. An optical pickup on a movable arm is positioned adjacent the surface of the disc by optical pickup and arm block 102, which receives control signals 114 from focus and radial tracking control block 104. Photodetector signal 112 generated from optical pickup and arm block 102 is provided to focus and radial tracking control block 104 and signal processor 105.
Drive control CPU (central processing unit) 106 monitors the data flow through signal processor 105 via signals 117, and provides servo control signals 116 to turn table motor control block 103 and focus and radial tracking control block 104. Drive control CPU 106 interfaces with control CPU 109 via signal lines 118 to receive track and index requests for directing the servo system of the CD-ROM drive.
Signal processor 105 demodulates the analog photodetector signal into a stream of binary bits, decodes the EFM data stream and performs descrambling and CIRC correction. Signal processor 105 provides decoded and descrambled digital data 119 to audio circuit 107 and ECC/EDC (error correction coding/error detection coding) processor 108. If the data on the compact disk is audio data, such as for a music CD, an optional audio circuit 107 may transform digital data 119 into analog audio output signal 120.
ECC/EDC processor 108 places digital data 119 from signal processor 105 into buffer memory 122 (RAM, typically 16 kB) and performs error correction before transmitting the corrected data over bus 125 to the host computer interface (I/F) card 111 in host computer 110. Sector address information extracted from the header in the data sector is provided to control CPU 109 over bus 125. Control signals 121 are exchanged between ECC/EDC processor 108 and control CPU 109 to control data transfers from ECC/EDC processor 108 across bus 125.
ECC/EDC processor 108 and I/F card 111 exchange request and acknowledge signals (123) when a processed sector is ready to be transferred from buffer 122 to I/F card 111. I/F card 111 and control CPU 109 also may communicate across bus 125, using control signals 124 to coordinate bus use. A software "driver" process, designed for the specific CD-ROM drive and resident in the host computer, provides the appropriate protocol for the host computer's CPU and I/F card to communicate with control CPU 109 and ECC/EDC processor 108.
The CD-ROM drive servo system, primarily comprising blocks 101-104 and 106, positions the optical pickup (i.e., laser diode and photodetector) above the appropriate track of the compact disc. The servo system is used for locating a specific sector of the compact disc and controlling motor spin, as well as for maintaining tracking and beam focus. Servo system implementations are further described in The Brady Guide to CD-ROM, by Laura Buddine and Elizabeth Young, published by Prentice Hall Press, New York, in 1987. The servo system descriptions of The Brady Guide to CD-ROM are incorporated herein by reference.
Signal 112 produced by the photodetector in response to the reflected laser beam is an analog signal modulated in proportion to the length of the pits and lands. In signal processor 105, analog signal 112 is converted into a binary digital signal, with a transition between lands and pits interpreted as a "1", and the intervals in between interpreted as "0's." Typically, Eight to Fourteen Modulation (EFM) is used to encode the information stored on the CD-ROM disc. Accordingly, when the data is read back from the disc, the fourteen-bit data is decoded into eight-bit format with an EFM lookup table in signal processor 105. Typically, subsequent to decoding, CIRC (cross-interleaved Reed-Solomon code) error correction is performed in block 105 to generate audio quality data 119 with a bit error rate on the order of 10.sup.-9 bits/second for scratched or dirty discs.
Compact discs are subject to errors from scratches, dust particles, fingerprints, and other sources of reading interference. These types of interference can result in long burst errors in the reading of the underlying disc tracks. Cross-coding and interleaving of data serves to break up long burst errors into very small errors or error bursts when the data is descrambled. Reed-Solomon codes are applied to the small error bursts to perform limited correction. The resulting corrected data out of the signal processor is of audio quality.
While blanking and interpolating of audio data can reduce errors so as to be substantially undetectable by the human ear, these processes are not satisfactory for CD-ROM data storage purposes which typically require a bit error rate of better than 10.sup.-12 bits/second. For this reason, further error correction, sometimes referred to as layered ECC, is performed in ECC/EDC processor 108.
ECC/EDC processor 108 stores several sectors of decoded data 119 in buffer 122 at any moment in time. ECC/EDC hardware performs error correction on the buffered data one sector at a time, transferring the corrected sectors to host computer 110 as they are completed. The software driver resident in the host computer interfaces with the operating system or other CD-ROM utility software to handle the transfer of incoming data through I/F card 111 into the host computer's RAM.
The decoded sector data 119 contains 2352 bytes of information arranged as follows:
______________________________________ Relative Byte Address Contents ______________________________________ -- 12 Data Sync Bytes 0-3 4 Header Bytes 4-2051 2048 Data Bytes 2052-2339 288 ECC/EDC Bytes ______________________________________
The first twelve bytes of the sector are used as data sync bytes. The first and last bytes of the sync field are 00.sub.hex, whereas the rest of the sync field bytes are FF.sub.hex. The header field contains the sector address and the mode byte. The first three bytes of the header are the minutes, seconds and sector, respectively, stored in binary coded decimal format. The mode byte indicates the nature of the data stored in the data field. For instance, zero mode indicates that the data field contains all 0's. Modes one and two indicate CD-ROM data with ECC/EDC (2,048 bytes of user data) and without ECC/EDC (2,336 bytes of user data), respectively.
The 288 ECC/EDC bytes contain four cyclical redundancy check (CRC) bytes followed by eight bytes of zeros. The CRC is a simple checksum calculated from the sync, header and data blocks by calculating a value of a polynomial on the three blocks. This constitutes the error detection coding (EDC) for the sector, and is ultimately compared with the value of the polynomial that is calculated after the error correction coding (ECC) has been applied. If the CRC bytes match the value calculated from the corrected data, it is assumed that all errors have been corrected. The CRC bytes provide only error detection, not correction.
The 276 bytes of ECC check bytes are used for Reed-Solomon coding. Reed-Solomon encoding/decoding algorithms involve polynomials calculated with a finite field arithmetic known as Galois Fields (GF). This process constructs one polynomial whose roots locate erroneous bytes, and another polynomial that gives the correction value to be added to the erroneous bytes. For CD-ROM, ECC is performed using forty-three independent (26,24) Reed-Solomon code words and twenty-six independent (45,43) Reed-Solomon code words over GF(2.sup.8).
The 2,064 bytes containing the header, user data, CRC and zero bytes are combined into 1,032 two-byte words having a "most significant byte" (MSB) and "least significant byte" (LSB). The MSB's and LSB's of the words are operated on as if they exist in two separate 43.times.24 arrays, designated as the LSB plane and the MSB plane. Column correction, called "P" correction, and diagonal correction, called "Q" correction, are each performed on both arrays. This dual correction scheme permits multiple uncorrectable errors in a single column to be corrected by the overlapping diagonal correction process, and vice versa.
FIG. 7 is a flow diagram of the general ECC correction process, which can be represented as nested loops. Beginning in block 700, the ECC/EDC processor is set for "P" correction. In the following block 701, the ECC/EDC processor is set to operate on the LSB plane of the chosen sector data. In block 702, the data is read from the buffer in the form of code words, and RSPC (Reed-Solomon Product Code) detection is performed to identify errors.
A branching occurs at decision block 703 based on whether errors were detected in the preceding detection phase. If no errors were detected, then the process continues in block 706. However, if errors were detected, then, in block 704, RSPC correction is performed on the erroneous code words, and, in subsequent block 705, the corrected bytes are written back to the buffer. After block 705, the process continues in block 706.
In block 706, a branching occurs based on the sector plane just completed. If the LSB plane was just completed, then, in block 707, the ECC/EDC processor is set for the MSB plane and the process returns to block 702. If the MSB plane was just completed, then, in decision block 708, another branching occurs based on which type of ECC correction was just performed.
If "P" correction was just performed, then, in block 709, the ECC/EDC processor is set for "Q" correction and the process returns to block 701. However, if "Q" correction was just completed, then, in block 710, a branching occurs based on whether any uncorrectable errors were reported during "P" or "Q" correction. If no uncorrectable errors were detected, then, in block 711, EDC detection is performed on the sector data using CRC check bytes. Subsequently, in block 712, the entire sector is written to the host computer. If, in block 710, uncorrectable errors were reported, then, in block 713, the correction process is repeated from block 700, or the ECC/EDC processor reports an uncorrectable error in the sector.
FIGS. 3A and 3B illustrate the LSB and MSB arrays respectively, showing the row and column positions of the relative addresses for the sector information. That portion of the array comprising the header, user data, CRC and zero bytes is indicated by the numeral 300. Numerals 301 and 302 indicate ECC data.
Address "0000" in FIG. 3A corresponds to the first byte of sector information, but does not typically correspond to physical address location "0000" in the buffer. The buffer may contain several sectors of information at any moment in time, accessing the appropriate sector information by specifying the physical address of the beginning of the sector, and adding a value comprising the relative address of the appropriate array location. Various schemes for mapping sectors into buffer memory are available, including modulo address generation.
Each column of the arrays in FIGS. 3A and 3B has two precalculated check bytes appended, and represents a single Reed-Solomon code word. There are 43 column code words, designated as "P" code words, in each array. By appending two bytes of ECC data (301) to each column, a new twenty-six row array is created (region 300 plus region 301) wherein the respective 43.times.24 array (300) is a subset. A second, independent set of code words is created by using the diagonals of the 43.times.26 array, starting with the first column and wrapping where necessary to obtain twenty-six new code words for each plane. These new code words are referred to as "Q" code words. Each "Q" code word also has two appended check bytes (302).
FIG. 3C illustrates a remapping of the LSB plane to define "Q" code words along the rows of the array. A remapping of the MSB plane could be similarly performed. The remapped 43.times.26 array is labelled with numeral 303, and includes all elements from regions 300 and 301 of FIG. 3A. Region 302 contains the "Q" code word ECC bytes. Addresses are circled in the diagram where a modulo operation of the array address space forces the "Q" code word address sequence to wrap through zero.
The "P" code words can be viewed as a twenty-six element column vector, wherein the first twenty-four elements are a column from region 300, and the last two elements are two bytes of ECC from the corresponding column in region 301. Each element consists of the memory contents at the indicated relative memory address in the array. In some texts, these elements of the code words are referred to as "symbols." A "P" code word may be represented generally as: ##EQU1## where n is the column number from 0-42, A(MSB)=1, and A(LSB)=0.
Similarly, the "Q" code words can be viewed as a forty-five element column vector, wherein the first forty-three elements are a row of region 303 (or a diagonal of regions 300 and 301), and the last two elements are two bytes of ECC from the corresponding rows in region 302 of FIG. 3C. Thus, a "Q" code word may be represented generally as: ##EQU2## where m is the row number from 0-25, A(MSB)=1, and A(LSB)=0.
Because the "P" and "Q" code words are constructed from interleaved bytes rather than consecutive bytes, special means are required to calculate the correct addresses when the code words are read from the buffer for ECC correction. The calculation of relative array addresses for the "P" and "Q" code word elements, as shown in the P(n) and Q(m) vector representations, requires two multiplication operations and at least one addition operation per address. In addition, the "Q" code words require a modulo operation. The amount of chip area and power required, as well as the time delay involved, for these calculations impinge on the cost and performance of the ECC/EDC circuit and thus the CD-ROM drive.